package day_2023_7_to_10;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2023/08/07 22:25
 **/
public class Day_8_7 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    class Solution {
        Node pre, head;
        public Node treeToDoublyList(Node root) {
            if(root == null) return null;
            treeToDoublyListHelper(root);
            head.left = pre;
            pre.right = head;
            return head;
        }
        public void treeToDoublyListHelper(Node root) {
            if(root == null) return;
            treeToDoublyListHelper(root.left);
            if(head == null) head = root;
            else {
                pre.right = root;
                root.left = pre;
            }
            pre = root;
            treeToDoublyListHelper(root.right);
        }
    }
    class Solution2 {
        public int kthLargest(TreeNode root, int k) {
            if(root == null) return -1;
            Deque<Integer> s = new LinkedList<>();
            preOrder(s, root);
            int[] arr = s.stream().mapToInt(Integer::intValue).toArray();
            for(int i : arr) System.out.print(i);
            while(k-- > 1) s.pop();
            return s.peek();
        }
        public void preOrder(Deque<Integer> s, TreeNode root) {
            if(root == null) return;
            preOrder(s, root.left);
            s.push(root.val);
            preOrder(s, root.right);
        }
    }

    class Solution3 {
        public int kthLargest(TreeNode root, int k) {
            if(root == null || k <= 0) return -1;
            Deque<TreeNode> s = new LinkedList<>();
            while(!s.isEmpty() || root != null) {
                while(root != null) {
                    s.push(root);
                    root = root.right;
                }
                TreeNode cur = s.pop();
                if(k-- == 1) return cur.val;
                root = cur.left;
            }
            return -1;
        }
    }

    class Solution4 {
        public int maxDepth(TreeNode root) {
            if(root == null) return 0;
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }

    class Solution5 {
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            int l = isBalancedHelper(root.left);
            int r = isBalancedHelper(root.right);
            return Math.abs(l-r) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
        public int isBalancedHelper(TreeNode root) {
            if(root == null) return 0;
            return 1 + Math.max(isBalancedHelper(root.left), isBalancedHelper(root.right));
        }
    }

    class Solution6 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return root;
            if(root == p || root == q) return root;
            if(root.val < p.val && root.val < q.val) {
                return lowestCommonAncestor(root.right, p, q);
            }else if(root.val > p.val && root.val > q.val) {
                return lowestCommonAncestor(root.left, p, q);
            }else return root;
        }
    }

    class Solution7 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return root;
            if(root == p || root == q) return root;
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if(l != null && r != null) return root;
            else if(l != null) return l;
            else if(r != null) return r;
            return null;
        }
    }
}